package com.algorithm.learning.base.动态规划;

/**
 * @program: algorithm-learning
 * @description:
 * @author: YuKai Fan
 * @create: 2024/9/3 21:45
 **/
public class 从左往右尝试模型2_背包模型 {


    /**
     * 给定两个长度都为N的数组weights和values
     * weight[i]和values[i]分别代表i号物品的重量和价值
     * 给定一个正数bag，表示一个载重bag的袋子
     * 你装的物品不能超过这个重量
     * 返回你能装下最多的价值是多少？
     * @param w 不变 weight数组
     * @param v 不变 value数组
     * @param index 最大价值
     * @param alreadyW 0..index-1上做了货物的选择，使得你已经达到的重量是多少
     * @param bag 背包大小
     * @return
     */
    public static int process(int[] w, int[] v, int index, int alreadyW, int bag) {
        // 当前重量已经超过了背包，那么返回-1，表示没有方案
        if (alreadyW > bag) {
            return -1;
        }
        // 重量没超, 但是index已经到了最后一个位置，表示当前重量已经到头且没有货物可以选，返回0，方案是可以的，只是价值为0
        if (index == w.length) {
            return 0;
        }
        // 可能性1，没有要当前index的货物，alreadyW没有往上加，直接递归下一个index
        int p1 = process(w, v, index + 1, alreadyW, bag);
        // 可能性2，要了当前index的货物，alreadyW加上当前index的货物重量，递归下一个index
        int p2Next = process(w, v, index + 1, alreadyW + w[index], bag);

        // 这里的p2表示，可能性2的情况下，也就是要了当前货物的情况下，它的总价值多少
        // 因为要了当前货物，那么已经达到的重量alreadyW是已经加上了，当前index的重量，但是当前货物的价值value没有加上
        // 所以当要了货物的情况下，如果方案有效(!= -1) ,那么就把可能性2的价值，加上当前价值就是总价值
        int p2 = -1;
        // 如果可能性2，也就是在要了当前货物的情况下，且方案是有效的，
        // 那么可能性2的总价值应该是，当前货物价值加上可能性2获取到的价值，就是总价值
        if (p2Next != -1) {
            p2 = v[index] + p2Next;
        }
        // 从这两种可能中选择一个最大的，也就是最好的情况
        // 可能1：没要货物，我的价值p1
        // 可能2：要了货物, 我的价值p2
        // 在这两种可能都有效的情况下，比较哪个一个价值最大
        return Math.max(p1, p2);
    }

    /**
     * 第二种方法，利用剩余空间来优化
     * @param w
     * @param v
     * @param index index.. 货物自由选择，但是剩余空间不能小于0
     * @param rest 表示，index货物做选择，bag中还剩下多少的重量
     * @return index..货物能够获得的最大价值
     */
    public static int process(int[] w, int[] v, int index, int rest) {
        // 剩余空间小于0，表示无效方案，返回-1
        if (rest < 0) {
            return -1;
        }
        // 还有剩余空间 rest >= 0
        if (index == w.length) {
            return 0;
        }

        // 可能性1：不要当前货物，所以剩余空间rest没有变
        int p1 = process(w, v, index + 1, rest);
        int p2 = -1;
        // 可能性2：要当前货物，所以剩余空间rest减去当前货物重量
        int p2Next = process(w, v, index + 1, rest - w[index]);
        if (p2Next != -1) {
            p2 = v[index] + p2Next;
        }
        return Math.max(p1, p2);
    }
}
